
#include "..\headers\ListOf.h"

// Define a node structure
typedef struct LNodeList {
  int data;
  struct LNodeList* next;
} LNodeList, *LinkList;

// Function to create a new node
LinkList createNode(int data) {
  LinkList newNode = (LinkList)malloc(sizeof(LNodeList));
  if (newNode == NULL) {
    printf("Memory allocation failed\n");
    exit(1);
  }
  newNode->data = data;
  newNode->next = NULL;
  return newNode;
}

// Function to insert a node at the end of the linked list
void insertEnd(LinkList& head, int data) {
  LinkList newNode = createNode(data);
  if (head == NULL) {
    head = newNode;
  } else {
    LinkList temp = head;
    while (temp->next != NULL) {
      temp = temp->next;
    }
    temp->next = newNode;
  }
}

// Function to check if an element exists in the linked list
bool exists(LinkList head, int key) {
  LinkList temp = head;
  while (temp != NULL) {
    if (temp->data == key) {
      return true;
    }
    temp = temp->next;
  }
  return false;
}

// Function to perform union of two linked lists
LinkList unionLists(LinkList head1, LinkList head2) {
  LinkList result = NULL;
  LinkList temp1 = head1;
  LinkList temp2 = head2;

  // Traverse list 1 and insert all elements into the result list
  while (temp1 != NULL) {
    insertEnd(result, temp1->data);
    temp1 = temp1->next;
  }

  // Traverse list 2 and insert elements into the result list if they don't
  // already exist
  while (temp2 != NULL) {
    if (!exists(result, temp2->data)) {
      insertEnd(result, temp2->data);
    }
    temp2 = temp2->next;
  }

  return result;
}

// Function to display a linked list
void displayList(LinkList head) {
  LinkList temp = head;
  while (temp != NULL) {
    printf("%d ", temp->data);
    temp = temp->next;
  }
  printf("\n");
}

// Function to free memory allocated for a linked list
void freeList(LinkList head) {
  LinkList temp;
  while (head != NULL) {
    temp = head;
    head = head->next;
    free(temp);
  }
}

int main() {
  LinkList head1 = NULL;
  LinkList head2 = NULL;
  int num, data;

  printf("Enter the number of elements in the first list: ");
  scanf("%d", &num);
  for (int i = 0; i < num; i++) {
    scanf("%d", &data);
    insertEnd(head1, data);
  }

  printf("Enter the number of elements in the second list: ");
  scanf("%d", &num);
  for (int i = 0; i < num; i++) {
    scanf("%d", &data);
    insertEnd(head2, data);
  }

  if (head1 == NULL && head2 == NULL) {
    printf("ERROR");
    return 0;
  }

  LinkList result = unionLists(head1, head2);

  displayList(result);

  // Free memory allocated for the lists
  freeList(head1);
  freeList(head2);
  freeList(result);

  return 0;
}
